from pythonds.node import SNode


class List:
    """单链表
    添加节点:无序链表与有序链表的添加数据方法不一样，具体方法有子类实现
    删除节点: 头部删除(pop)、中间删除(remove);尾部删除效率与remove(效率相同，由remove(len(ls)-1)实现)
    查找节点: 按内容search()
    索引节点: 返回一个引用，可以直接修改链表数据
    """

    def __init__(self):
        self._head = SNode()  # 头指针
        # 头部节点的维护：1）插入第一个节点;2）删除最后一个节点
        self._tail = SNode()  # 尾指针,加速尾插
        # 尾部节点的维护：1)尾部节点的删除，前移一个或置空; 2)添加第1个元素; 3)尾部插入
        self._size = 0

    def empty(self) -> bool:
        return 0 == self._size

    def __len__(self):
        return self._size

    @property
    def size(self) -> int:
        return self._size

    def __iter__(self):
        self._cur = self._head  # 迭代器指针
        return self

    def __next__(self):
        self._cur = self._cur.next
        if self._cur is not None:
            return self._cur.data
        else:
            raise StopIteration

    def items(self):
        if self.empty():
            yield None

        cur = self._head.next
        while cur is not None:
            yield cur.data
            cur = cur.next

    # 类似数组的索引pos：
    # _get_pre_pos, 返回pos位置前的节点
    # __getitem__, 返回pos位置的节点数据，表现为[]索引
    # __setitem__, 修改pos位置处的节点的数据
    # delete, 删除第pos个节点
    # index, 返回节点的索引数, 类似于list类型的index

    def _get_pre_pos(self, pos: int, default=None):
        """返回pos位置前的节点, 是对内方法。
        内部表现为0为头节点, 1为第1个节点, 主要是为了方便插入与添加不用寻找前一节点
        Args:
            pos (int): 位置。
            default (_type_, optional): 用于get函数.

        Returns:
            _type_: 返回pos位置前的节点
        """
        if pos > self._size or pos < 0:
            return default

        p = self._head
        for i in range(pos):
            p = p.next
        return p

    def __getitem__(self, pos: int):
        """返回第pos个节点存储的数据

        Args:
            pos (int): 位置。0返回头节点;1返回第1个节点。

        """
        p = self._get_pre_pos(pos + 1)
        if p is not None:
            return p.data
        else:
            return None

    def __setitem__(self, pos: int, value) -> bool:
        """修改pos位置处的节点的数据

        Args:
            pos (int): 位置
            value (_type_):

        Returns:
            bool: 返回是否修改成功
        """
        p = self._get_pre_pos(pos + 1)
        if p is None:
            return False
        p.data = value
        return True

    def delete(self, pos: int) -> bool:
        """删除第pos个节点, 从0数"""
        # 找到第pos个位置的前一个位置
        p = self._get_pre_pos(pos)
        if (p is None) or (p.next is None):
            print("删除位置越界，操作失败")
            return False

        # 删除当前节点
        t = p.next
        p.next = t.next
        self._size -= 1
        del t

        # 从头部计数，需要维护尾指针
        if pos == self._size:  # 删除的是最后一个元素
            if self.empty():
                self._tail.next = None
            else:
                self._tail.next = p

        return True

    def index(self, item) -> int:
        """返回节点的索引数"""
        if self.empty():
            return -1

        cur: SNode = self._head.next
        cnt = 0
        while cur is not None:
            if cur.data == item:
                return cnt
            cur = cur.next
            cnt += 1

        return -1

    # 基于节点引用的操作
    # _search_pre_node, 返回查找节点前一个节点的引用
    # search, 返回查找节点的引用
    # remove, 移除数据为item的节点
    # pop, 取得头节点的数据
    def _search_pre_node(self, item):
        """返回查找节点前一个节点的引用，方便修改与删除
        返回值：
        cur.next = None 未找到
        """

        cur: SNode = self._head
        while (cur.next is not None) and (cur.next.data != item):
            cur = cur.next

        return cur

    def search(self, item):
        """返回查找节点的引用，可以快速修改节点"""
        cur = self._search_pre_node(item)

        if cur.next is None:
            return None

        return cur.next

    def remove(self, item) -> bool:
        """移除数据为item的节点
        Returns:
            bool: 是否移除成功
        """
        cur = self._search_pre_node(item)

        if cur.next is None:
            print("链表中无{}，移除失败".format(item))
            return False

        t = cur.next
        cur.next = t.next
        del t

        self._size -= 1
        return True

    def pop(self):
        """取得头节点的数据"""
        if self.empty():
            print("链表为空，弹出失败")
            return False

        t = self._head.next
        self._head.next = t.next

        self._size -= 1
        return t.data


class UnorderedList(List):
    """无序链表
    插入节点：头部插入(add)、尾部插入(append)、中间插入(insert)
    """

    def __init__(self):
        super().__init__()

    def add(self, item):
        node = SNode(item)
        node.next = self._head.next
        if self.empty():  # 从头部插入，需要维护尾指针，,只需要维护插入的是第1个节点情况
            self._tail.next = node

        self._head.next = node

        self._size += 1

    def append(self, item):

        node = SNode(item)
        if self.empty():
            self._tail.next = node
            self._head.next = node  # 从尾部插入，需要维护头指针,只需要维护插入的是第1个节点情况
        else:
            self._tail.next.next = node

        self._tail.next = node

        self._size += 1

    def insert(self, pos: int, item) -> bool:
        # 找到第pos个位置的前一个位置
        p = self._get_pre_pos(pos)

        if p is None:
            print("插入位置越界，操作失败")
            return False

        node = SNode(item)
        t = p.next
        p.next = node
        node.next = t
        self._size += 1

        # 从头部计数，需要维护尾指针
        if node.next is None:
            self._tail.next = node
        return True


class OrderedList(List):
    """有序链表
    插入节点：insert
    """

    def __init__(self, asc=True):
        self._asc = asc
        super().__init__()

    def insert(self, item):
        node = SNode(item)

        # 从链表头始找，只需要维护尾指针
        cur = self._head

        # 如果是空表直接插入
        if cur.next is None:
            cur.next = node
            self._tail.next = node  # 维护尾指针
            return

        while (cur.next is not None) and asc_comp(cur.next.data, item, self._asc):
            cur = cur.next

        node.next = cur.next
        cur.next = node

        if node.next is None:  # 维护尾指针
            self._tail.next = node

    def _search_pre_node(self, item):
        """返回查找节点前一个节点的引用，方便修改与删除
        返回值：
        cur.next = None 未找到
        """

        cur: SNode = self._head
        while (cur.next is not None) and asc_comp(cur.next.data, item, self._asc):
            cur = cur.next

        if cur.next.data == item:
            return cur
        return SNode()

    # def search(self, item):
    #     """返回查找节点的引用，可以快速修改节点"""
    #     cur = self._search_pre_node(item)

    #     if cur.next == None:
    #         return None

    #     return cur.next


def asc_comp(item1, item2, asc=True):
    if asc:
        return item1 < item2

    return item1 > item2
